package crp.logic.clustering;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.Map.Entry;

import crp.object.SymmMatrix;

import edu.stanford.nlp.math.ArrayMath;
/**
 * This class is the main frame for the Non-Exhaustive Overlapping Clustering
 * 
 * @author ouhang
 */
public class NEOClusterFactory {

	/**
	 * Give a correlation matrix, when the correlation is larger than Ts,
	 * then set to 1, otherwise set to 0
	 * 
	 * @param corrlM correlation matrix
	 * @param Ts threshold of similarity
	 * @return
	 */
	public SymmMatrix computeBinaryM(SymmMatrix corrlM, double Ts){
		SymmMatrix binaryM = new SymmMatrix(corrlM.dim);
		for(int i = 0 ; i < binaryM.symM.length ; i++){
			if(corrlM.symM[i] > Ts) binaryM.symM[i] = 1.0;
			else binaryM.symM[i] = 0.0;
		}
		return binaryM;
	}
	
	public int[] initialCenter(int centerNum, SymmMatrix distMa, 
			SymmMatrix binaryMa, double[] cvs, double[] mdvs, double[] crf, double w1, double w2){
		//assume that all objects are old centers
		int[] clusterNum = computeClusterNumber(binaryMa);
		System.out.println();
		double[] nds = computeNds(distMa);
		
		double max = ArrayMath.max(clusterNum);
		for(int i = 0 ; i < cvs.length ; i++) cvs[i] = clusterNum[i] / max;
		
		max = ArrayMath.max(nds);
		for(int i = 0 ; i < mdvs.length ; i++) mdvs[i] = nds[i] / max;
		
		for(int i = 0 ; i < crf.length ; i++)
			crf[i] = w1 * cvs[i] + w2 * mdvs[i];
		
		nds = null; clusterNum = null;
		//generate new centers by the value of CRF
		int[] newcenters = new int[centerNum];
		double[] intervals = new double[crf.length];
		double[] crftemp = nomonize(crf.clone());
		
		intervals[0] = crftemp[0];
		for(int i = 1 ; i < intervals.length ; i++)
			intervals[i]  = intervals[i-1] + crftemp[i];
		//select centers randomly
		for(int i = 0 ; i < newcenters.length ; i++){
			double temp = Math.random() * intervals[intervals.length-1];
			int index = 0;
			for(int j = 0 ; j < intervals.length ; j++)
				if(temp < intervals[j]){
					index = j;
					break;
				}
			newcenters[i] = index;
			//check whether this center has been chosen
			for(int j = 0 ; j < i ; j++)
				if(newcenters[j] == index){
					newcenters[i] = -1; i--; break;
				}
		}
		return newcenters;
	}
	
	public double clusteringStepreplaceCenter(int[] centers, SymmMatrix distMa, 
			double[]cvs, double[] mdvs, double[] crf, double w1, double w2, double oldObject){
		//select one new cluster center to replace the old one 
		//and this new one should not be an old center
		double[] intervals = new double[crf.length - centers.length];
		int[] indexes_reserve = new int[intervals.length];
		double[] crftemp = nomonize(crf.clone());
		int counter = 0;
		for(int i = 0 ; i < crf.length ; i++){
			//check whether is the center
			boolean flag = false;
			for(int j = 0 ; j < centers.length ; j++)
				if(centers[j] == i){
					flag = true;
					break;
				}
			if(flag) continue;
			intervals[counter] = crftemp[i];
			indexes_reserve[counter++] = i;
		}
		for(int i = 1 ; i < intervals.length ; i++)
			intervals[i] += intervals[i-1];
		int newcenter = 0;
		//pick new center
		double temp = Math.random() * intervals[intervals.length-1];
		newcenter = 0;
		for(int j = 0 ; j < intervals.length ; j++)
			if(temp < intervals[j]){
				newcenter = indexes_reserve[j];
				break;
			}

		indexes_reserve = null;
		intervals = null;
		/*//it will replace the nearest center from it
		double[] dist = new double[centers.length];
		for(int i = 0 ; i < dist.length ; i++)
			dist[i] = distMa.getValue(centers[i], newcenter);
		//get the nearest center with it
		//notice the distance between one and oneself is INF
		int cIndex = ArrayMath.argmin(dist);//*/
		Random rand = new Random();
		int cIndex = rand.nextInt(centers.length);
		
		//replace center
		double value = replaceCenter(newcenter, cIndex, centers, cvs, mdvs, crf, w1, w2, oldObject);
		/*System.out.println("Centers: ");
		for(int i = 0 ; i < centers.length ; i++) System.out.print(centers[i]+" ");
		System.out.println();//*/
		//System.out.println(value);
		return value;
	}
	
	/**
	 * !The objective function.
	 * Objective value the larger, the better. 
	 * objective  = w1 * min(Mdv) + w2 * sum(cvs) / k
	 * k: center number
	 * CV(xi) = nxi / nmax: the larger the better
	 * nxi: number of objects in cluster center xi
	 * nmax: the maximum number of objects in all clusters
	 * 
	 * MDv(xi) = ndxi / maxd: the larger the better
	 * ndxi: the nearest distance from object to center xi
	 * maxd: the maximum distance of all ndxi-s of all clusters
	 */
	public double computeObj(double[] mdx, double[] cvs, double w1, double w2){

		return w1 * ArrayMath.min(mdx) + w2 * ArrayMath.sum(cvs) / cvs.length;
	}
	
	private double[] getDist(int center, SymmMatrix distMa){
		double[] dist = new double[distMa.dim-1];
		int counter = 0;
		for(int i = 0 ; i < distMa.dim ; i++){
			if(center == i) continue;
			dist[counter++] = distMa.getValue(center, i);
		}
		return dist;
	}//*/

	private int[] computeClusterNumber(SymmMatrix binaryMa){
		int[] cns = new int[binaryMa.dim];//center number
		 for(int i = 0 ; i < binaryMa.dim ; i++){
				int sum = 0;
				for(int j = 0 ; j < binaryMa.dim ; j++)
					if(binaryMa.getValue(i, j) == 1.0) sum++;
				cns[i] = sum;
			}
		return cns;
	}
	
	/**
	 * Calculate Ts, which is the median of the matrix
	 * @param sm
	 * @return
	 */
	public double calculateTs(SymmMatrix sm){
		ArrayList<Double> al = new ArrayList<Double>();
		for(double temp:sm.symM)
			if(temp >= 0) al.add(temp); 
		double[] tempp = new double[al.size()];
		for(int i = 0 ; i < al.size() ; i++) tempp[i] = al.get(i);
		return ArrayMath.median(tempp);
	}//*/
	
	/**
	 * compute nearest distance of each object
	 * @param distMa
	 * @return
	 */
	private double[] computeNds(SymmMatrix distMa){
		double[] nds = new double[distMa.dim];
		for(int i = 0 ; i < distMa.dim ; i++){
			double[] distM = getDist(i, distMa);
			nds[i] = ArrayMath.min(distM);
			//if(nds[i] == 1.0E7)
				//System.out.println();
		}
		return nds;
	}
	
	/**
	 * Compute the CRF (Cluster Recommending Factor) of center xi
	 * 
	 * CRF(xi) = w1 * CV(xi) + w2 * MDv(xi)
	 * 
	 * CV(xi) = nxi / nmax: the larger the better
	 * nxi: number of objects in cluster center xi
	 * nmax: the maximum number of objects in all clusters
	 * 
	 * MDv(xi) = ndxi / maxd: the larger the better
	 * ndxi: the nearest distance from object to center xi
	 * maxd: the maximum distance of all ndxi-s of all clusters
	 * 
	 */
	
	
	/**
	 * This method is used for replace the centers
	 * @param newcenter new center
	 * @param cIndex index of old center that to be replaced
	 * @param cp store cluster parameters
	 * @param distMa distance matrix
	 * @param binaryM binary matrix
	 * @param w1 threshold 
	 * @param w2 threshold
	 * @param oldObject old objective value
	 * @return new objective value
	 */
	private double replaceCenter(int newcenter, int cIndex, int[] centers, 
			double[] cvs, double[] mdvs, double[] crf, double w1, double w2, double oldObject){
		

		double[] mdvstemp = new double[centers.length];
		double[] cvstemp = new double[centers.length];
		for(int i = 0 ; i < mdvstemp.length ; i++) mdvstemp[i] = mdvs[centers[i]];
	
		if(mdvs[newcenter] < ArrayMath.min(mdvstemp) && cvs[newcenter] < cvs[centers[cIndex]]) return oldObject;
		
		//replace the center
		int oldcenter = centers[cIndex];
		centers[cIndex] = newcenter;
		
		for(int i = 0 ; i < mdvstemp.length ; i++) cvstemp[i] = mdvs[centers[i]];
		mdvstemp[cIndex] = mdvs[centers[cIndex]];
		
		//calculate the objective value
		double newObject = computeObj(mdvstemp, cvstemp, w1, w2);
		
		
		
		if(newObject > oldObject){
			return newObject;
		}else{
			centers[cIndex] = oldcenter;
			return oldObject;
		}
	}
	
	private double[] nomonize(double[] vector){
		double result[] = new double[vector.length];
		
		double min = INF;
		
		for(double temp:vector)
			if(temp < min && temp != 0)
				min = temp;
		
		
		for(int i = 0 ; i < vector.length ; i++)
			result[i] = vector[i] + min / 10;
		return result;
	}
	
	public static double INF = 10000000;
}
